package cn.edu.neu.softlab.jason.offer.jianzhioffer.datastructure;

import jdk.nashorn.internal.ir.annotations.Ignore;

/**
 * 剑指offer-面试9
 * 菲波那切数列
 * 写一个函数，输入n，求菲波那切数列的第n项。菲波那切数列的定义如下。
 * f(n) = 0                   n = 0
 *      = 1                   n = 1
 *      = f(n-1) + f(n-2)     n>=2
 */
public class Mianshi9 {
    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            System.out.print(fibonacciLoop(i) + " ");
        }
        System.out.println();
        for (int i = 0; i < 10; i++) {
            System.out.print(fibonacciRecursion(i) + " ");
        }
        System.out.println(fibonacciOfferwithMatrix(9));
    }

    public static int fibonacciLoop(int n) {
//        if (n == 0) {
//            return 0;
//        } else if (n == 1) {
//            return 1;
//        }
        int[] fibo = {0, 1};
        if (n < 2) {
            return fibo[n];
        }
        for (int i = 2; i < n + 1; i++) {
            fibo[i % 2] = fibo[0] + fibo[1];
        }
        return fibo[n % 2];
    }

    public static int fibonacciRecursion(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1){
            return 1;
        }
        return fibonacciRecursion(n - 1) + fibonacciRecursion(n - 2);
    }

    private static int fibonacciOfferwithMatrix(int n) {
        return fibonacciwithMarix(n - 1)[0][0];
    }
    private static int[][] fibonacciwithMarix(int n) {
        int[][] ori = {{1, 1}, {1, 0}};
        if (n / 2 == 0) {
            return ori;
        }
        int[][] tmp = fibonacciwithMarix(n / 2);
        int[][] result = multiMatrix(tmp, tmp);
        if (n % 2 == 1) {
            return multiMatrix(result, ori);
        }
        return result;
    }

    private static int[][] multiMatrix(int[][] a, int[][] b) {
        int[][] result = new int[2][2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                result[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
            }
        }
        return result;
    }
}
